POST (E. L.)


POST (E. L.)
POST (E. L.)

POST EMIL LEON (1897-1954)

Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États-Unis en 1904, Emil Post obtint son Ph.D. à l’université Columbia de New York en 1920. Il était membre de l’American Mathematical Society depuis 1918 et de l’Association for Symbolic Logic dès sa fondation en 1935.

Sa thèse de doctorat, publiée en 1921, porte sur le calcul propositionnel de A. N. Whitehead et B. Russell dont il montre la consistance et le caractère complet. Ici, consistance et complétude sont définies de façon syntaxique. C’est le début de la théorie moderne de la démonstration. (Une théorie est consistante au sens de Post si aucune variable propositionnelle n’est démontrable, et une théorie est complète si toute formule devient démontrable si l’on ajoute aux axiomes une formule non démontrable.) Pour arriver à ces résultats, il utilise cependant la méthode «sémantique» des tables de vérité. Il examine ensuite les logiques à plusieurs valeurs à l’époque où I. Lukasiewicz étudiait, de façon plus philosophique que mathématique, les logiques à trois valeurs. En 1925, poursuivant les travaux de sa thèse, il cherche à montrer le caractère incomplet du système des Principia Mathematica de Russell et Whitehead. Les résultats qu’il obtient ainsi sont contenus dans ceux que K. Gödel et A. Church obtiendront dans les années 1930. Ses principaux travaux sont ensuite consacrés à l’étude des processus effectifs que l’on rencontre en mathématiques.

Ainsi, en 1947, il résout, en même temps que A. A. Markov, le problème posé par A. Thue en 1914 de savoir s’il existe un algorithme permettant de décider, étant donné un mot sur un alphabet fini et un système fini de relations entre des mots sur cet alphabet, si le mot donné est équivalent à l’identité dans le monoïde quotient du monoïde libre par la plus petite congruence compatible avec les relations données.

Pour montrer qu’il n’existe pas de tel algorithme, il introduit ce que l’on appelle les systèmes de Post, grâce auxquels on peut exprimer (comme avec les machines de Turing, les algorithmes de Markov, etc.) le calcul de n’importe quelle fonction récursive. Ce résultat de Post est équivalent à la non-résolubilité du problème des mots, que l’on peut formuler de la façon suivante: soient L(X) et L(Y) deux monoïdes libres ayant un nombre fini de générateurs. Dès que [X] 閭 3, il n’existe pas d’algorithme permettant de décider si deux morphismes (f , g ) de L(X) vers (Y) ont une solution commune (un z 捻 L(X) tel que f (z ) = g (z ); f et g sont donnés par leurs valeurs sur X). Ce résultat de Post a été affiné par M. L. Minsky en 1966, qui considère le cas où f est épimorphisme (Post-Tag problem ), et enfin par Y. Lecerf en 1967, qui impose à f et g d’être tous les deux des épimorphismes.

Ce sont ces différents résultats d’indécidabilité qui sont à la base de ceux que l’on rencontre dans la théorie des grammaires formelles.

Pour terminer, indiquons ce que W. Quine écrivait en 1954 à l’occasion de la mort de Post: «Le concept de fonction récursive, concept mathématique précis rendant compte de la notion de calculabilité, fut découvert indépendamment et sous des formes différentes par quatre mathématiciens et Post fut l’un d’entre eux», et, en 1972, W. Quine ajoutait: «La théorie des fonctions récursives dont Post fut un des cofondateurs est deux fois plus âgée qu’en 1954; elle a bien montré, depuis, quel champ fertile elle est.»

Encyclopédie Universelle. 2012.

Regardez d'autres dictionnaires:

  • post — post …   Dictionnaire des rimes

  • Post-it® — Post it® …   Deutsch Wörterbuch

  • Post- — Post …   Deutsch Wörterbuch

  • post — post·abdomen; post·absorptive; post·age; post·al·ly; post; post·anoxic; post·antennal; post·arteriolar; post·atomic; post·audit; post·axial; post·bellum; post·brachium; post·branchial; post·breeding; post·canonical; post·cardinal; post·cava;… …   English syllables

  • post- — ♦ Élément, du lat. post « après », dans le temps (postdater) et dans l espace (postposer). post élément, du lat. post, après . ⇒POST , préf. Préf. tiré de la prép. lat. post «après», entrant dans la constr. de nombreux termes sav. ou techn., des… …   Encyclopédie Universelle

  • POST — bezeichnet: Postdienstleister und deren Beförderungsgüter, siehe Post, speziell die Deutsche Post AG die Österreichische Post Die Schweizerische Post eine Stadt im US amerikanischen Bundesstaat Texas, siehe Post (Texas) eine Mitteilung in… …   Deutsch Wikipedia

  • Post — Post, n. [F. poste, LL. posta station, post (where horses were kept), properly, a fixed or set place, fem. fr. L. positus placed, p. p. of ponere. See {Position}, and cf. {Post} a pillar.] 1. The place at which anything is stopped, placed, or… …   The Collaborative International Dictionary of English

  • Post-it — est une marque utilisée notamment pour une petite feuille de papier autoadhésive amovible, rassemblée en petit bloc, inventé en 1977[1] par la société américaine 3M. Il est conçu pour pouvoir y inscrire des notes et les coller et décoller à… …   Wikipédia en Français

  • Post — Saltar a navegación, búsqueda La palabra de origen latino post puede referirse a: En el vocablo español post ó pos , es un prefijo que significa después de o simplemente después. Por ejemplo: posparto, posgrado, posponer. El Diccionario… …   Wikipedia Español

  • Post — Prefix with Latin origin meaning after .Post may refer to: * An entry in a blog or internet forum (also see: posting style) * Mail, the postal system, especially in Commonwealth of Nations countries * Pole, a long and straight stick, usually… …   Wikipedia

  • Post — Post, n. [AS., fr. L. postis, akin to ponere, positum, to place. See {Position}, and cf. 4th {Post}.] 1. A piece of timber, metal, or other solid substance, fixed, or to be fixed, firmly in an upright position, especially when intended as a stay… …   The Collaborative International Dictionary of English